package 剑指offer;

public class _46把数字翻译成字符串 {
	public static void main(String[] args) {
		System.out.println("ab".substring(0,2));
	}
	/**
	 * 
	 *@time 2021年3月19日上午9:47:54
	 * 
	 *@param num
	 *@return int
	 *
	 *@see  若 xi和xi-1 组成的两位数字可以被翻译，则 dp[i] = dp[i - 1] + dp[i - 2]
	 *否则 dp[i] = dp[i - 1]dp[i]=dp[i−1]
	初始状态：dp[0]=dp[1]=1 ，即 “无数字” 和 “第 11 位数字” 的翻译方法数量均为 11 ；
	返回值： dp[n] ，即此数字的翻译方案数量。
	 无数字情况 dp[0] = 1
	Q:dp[0]=1 从何而来？
	A： 当 num 第 1,2 位的组成的数字∈[10,25] 时，显然应有 2 种翻译方法
	即 dp[2] = dp[1] + dp[0] = 2
	 */
    public int translateNum(int num) {
    	String s = String.valueOf(num);
    	int a=1,b=1;
    	for (int i = 2; i <= s.length(); i++) {//这里是因为s=s.length（）是因为下面的切割函数是从0-s.length（）
			String temp = s.substring(i-2,i);
			int c = temp.compareTo("10")>=0&&temp.compareTo("25")<=0 ? a+b : a;
			b=a;
			a=c;
		}
    	return a;
    }
    /***
     * 
     *@time 2021年3月19日上午10:01:16
     * 
     *@param num
     *@return int
     *
     *@see 上面的方法是较为不明显的动态规划
     */
    public int translateNum1(int num) {
    	String s = String.valueOf(num);
    	int []dp = new int [s.length()+1];
    	dp[0] = dp[1] = 1;
    	for (int i = 2; i <= s.length(); i++) {
			String temp = s.substring(i-2,i);
			dp[i]= temp.compareTo("10")>=0&&temp.compareTo("25")<=0 ? dp[i-2]+dp[i-1] : dp[i-1];
			
		}
    	return dp[s.length()];
    }

}
